package algorithm.t202112;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/8 9:12
 * @description :2道
 * 看了一天的房子，头疼，唉，钱在这个社会上的用处太大了，不可否认，
         “我们最终都要远行，
         最终都要跟稚嫩的自己告别。
         也许路途有点艰辛，
         有点孤独，
         但熬过了痛苦，
         我们才能得以成长。”
    致未来的自己：耐心，忍耐，勤勉，希望，信仰，自律。数十年如一，奋斗向前。
 persevere to last
 2021.12.8
 李红磊
 2021年12月8日21:20:55
 */
public class t20211208 {

    //689.三个无重叠子数组的最大和
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1 = 0, max_sum1 = 0, max_sum1_idx = 0;
        int sum2 = 0, max_sum12 = 0, max_sum12_idx1 = 0, max_sum12_idx2 = 0;
        int sum3 = 0, total = 0;

        for (int i = 2 * k; i < nums.length; i++) {
            sum1 += nums[i - 2 * k];
            sum2 += nums[i - k];
            sum3 += nums[i];

            if (i >= 3 * k - 1) {
                if (sum1 > max_sum1) {
                    max_sum1 = sum1;
                    max_sum1_idx = i - 3 * k + 1;
                }
                if (sum2 + max_sum1 > max_sum12) {
                    max_sum12 = sum2 + max_sum1;
                    max_sum12_idx1 = max_sum1_idx;
                    max_sum12_idx2 = i - 2 * k + 1;
                }
                if (max_sum12 + sum3 > total) {
                    total = max_sum12 + sum3;
                    ans[0] = max_sum12_idx1;
                    ans[1] = max_sum12_idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - 3 * k + 1];
                sum2 -= nums[i - 2 * k + 1];
                sum3 -= nums[i - k + 1];
            }

        }
        return ans;
    }

    private int[] tes(int[] nums, int k) {
        int[] ans = new int[1];
        int sum = 0, maxSum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (i >= k - 1) {
                if (sum > maxSum) {
                    maxSum = sum;
                    ans[0] = i - k + 1;
                }
                sum -= nums[i - k + 1];
            }
        }
        return ans;
    }

    private int[] tes2(int[] nums, int k) {
        int[] ans = new int[2];
        int sum1 = 0, max_sum1 = 0, max_sum1_idx = 0;
        int sum2 = 0, max_sum12 = 0;

        for (int i = k; i < nums.length; i++) {
            sum1 += nums[i - k];
            sum2 += nums[i];

            if (i >= 2 * k - 1) {
                if (sum1 > max_sum1) {
                    max_sum1 = sum1;
                    max_sum1_idx = i - 2 * k + 1;
                }
                if (sum2 + max_sum1 > max_sum12) {
                    max_sum12 = sum2 + max_sum1;
                    ans[0] = max_sum1_idx;
                    ans[1] = i - k + 1;
                }

            }
            sum1 -= i - 2 * k + 1;
            sum2 -= i - k + 1;
        }

        return ans;
    }

    //329.矩阵中的最长递增路径
    int rows, columns;
    int[][] memory;
    int[] dir = {-1, 0, 1, 0, -1};
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        rows = matrix.length;
        columns = matrix[0].length;
        memory = new int[rows][columns];
        int ans = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                ans = Math.max(ans, dfs(i, j, matrix));

            }
        }
        return ans;
    }
    private int dfs(int x, int y, int[][] matrix) {
        if (memory[x][y] != 0) return memory[x][y];
        memory[x][y]++;

        for (int i = 0; i < 4; i++) {
            int new_x = x + dir[i];
            int new_y = y + dir[i + 1];
            if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < columns && matrix[new_x][new_y] > matrix[x][y])
                memory[x][y] = Math.max(memory[x][y], dfs(new_x, new_y, matrix) + 1);


        }
        return memory[x][y];

    }

    public static void main(String[] args) {
        t20211208 t20211208 = new t20211208();
        System.out.println(t20211208.longestIncreasingPath(new int[][]{
                {2, 4, 6},
                {8, 2, 0}
        }));
    }


}
